/*
https://leetcode.cn/problems/numbers-with-repeated-digits
*/
class Solution {
public:
    // 函数 atMostNGivenDigitSet 接受一个字符串向量 digits 和一个整数 n 作为参数，
    // 返回由 digits 中的数字组成且不超过 n 的正整数的数量。
    int atMostNGivenDigitSet(vector<string>& digits, int n) {
        // 将整数 n 转换为字符串 s
        string s = to_string(n);
        // 获取 n 的长度 m 和 digits 的大小 sz
        int m = s.size(), sz = digits.size();
        
        // 定义深度优先搜索函数 dfs
        function<int(int, bool, bool)> dfs = [&](int i, bool is_full, bool is_num) -> int {
            // 如果已经遍历到字符串 s 的末尾
            if (i == m) {
                // 如果已经形成了一个合法的数字，则返回 1，否则返回 0
                return (int)is_num;
            }
            
            // 如果当前不是完全匹配状态，并且已经形成了一个数字
            if (!is_full && is_num) {
                // 直接返回剩余位置可以填入的数字数量
                return (int)pow(sz, m - i);
            }
            
            int res = 0;
            // 如果还没有形成一个数字，可以选择跳过当前位置
            if (!is_num) {
                res = dfs(i + 1, false, false);
            }
            
            // 计算当前位的下限和上限
            int lo = is_num ? 0 : 1;  // 如果已经形成了一个数字，下限为 0；否则为 1（不能以 0 开头）
            int hi = is_full ? s[i] - '0' : 9;  // 如果是完全匹配状态，上限为 s[i]；否则为 9
            
            // 遍历 digits 中的每个数字
            for (auto xx : digits) {
                int x = xx[0] - '0';  // 将字符转换为数字
                // 如果当前数字在允许范围内
                if (x <= hi && x >= lo) {
                    // 递归调用 dfs，更新 is_full 和 is_num 状态
                    res += dfs(i + 1, is_full && x == hi, true);
                }
            }
            return res;
        };
        
        // 从第 0 位开始，初始时是完全匹配状态，但还未形成一个数字
        return dfs(0, true, false);
    }
};